#include <stdio.h>
#include <stdlib.h>

#define flag 0

typedef int DataType;

typedef struct link_node
{
    DataType data;
    struct link_node *next;
} Lnode, *LinkList;

// 头插法
LinkList Create_LinkList() 
{
  LinkList L = NULL; // 建立空链表L
  Lnode *s;
  DataType e; // 设数据元素的类型为 datatype
  scanf("%d", &e); // 读取输入并存储到e中
  while(e != flag)
  {
    s = (Lnode *)malloc(sizeof(Lnode));
    s->data = e;
    s->next = L;
    L = s;
    scanf("%d", &e); // 读取输入并存储到e中
  }
  return L;
}

// 尾插法
LinkList Create_LinkList2() 
{
  LinkList L = NULL; // 建立空链表L
  Lnode *s, *r = NULL;
  DataType e; // 设数据元素的类型为 datatype
  scanf("%d", &e); // 读取输入并存储到e中
  while(e != flag)
  {
    s = (Lnode *)malloc(sizeof(Lnode));
    s->data = e;
    if (L == NULL) {
      L = s;
    } else {
      r->next = s;
    }
    r = s;
    scanf("%d", &e); // 读取输入并存储到e中
  }
  if (r != NULL) {
    r->next = NULL;
  }
  return L;
}

// 求链表长（带头结点）
int Length_LinkList(LinkList L) // 当链表带头结点时
{
  Lnode *p = L; // p 指向头指针
  int i = 0; // 设计数器 
  while (p->next) 
  {
    p = p->next;
    i++;
  }
  return i;
}

// 求链表长（不带头结点）
int Length_LinkList2(LinkList L) // 当链表不带头结点时
{
  Lnode *p = L; // p 指向头指针
  int i = 0; // 设计数器 
  if (p == NULL) return 0;
  i = 1; // 无头结点时，i从0开始 | 非空表，p指向第一个结点
  while (p) {
    p = p->next;
    i++;
  }
  return i;
}


// 按序号查找
Lnode *Get_LinkList(LinkList L, int i) 
{
  Lnode *p = L;
  int j = 0;
  while (p->next != NULL && j < i) 
  {
    p = p->next;
    j++;
  }
  if (j == i) 
    return p;
  else 
    return NULL;
}

// 按值查找
Lnode *Locate_LinkList(LinkList L, DataType x) 
{
  Lnode *p = L->next;
  while (p != NULL && p->data != x) 
  {
    p = p->next;
  }
  return p;
}

// 单链表插入操作，后插法
int Insert_LinkList(LinkList L, int i, DataType x) 
{
  Lnode *p, *s;
  p = Get_LinkList(L, i - 1);
  if (p == NULL) 
  {
    printf("参数i有误！\n");
    return 0;
  }
  s = (Lnode *)malloc(sizeof(Lnode));
  s->data = x;
  s->next = p->next;
  p->next = s;
  return 1;
}

// 单链表插入操作，前插法
int Insert_LinkList2(LinkList L, int i, DataType x) 
{
  Lnode *p, *s;
  p = Get_LinkList(L, i - 1);
  if (p == NULL) 
  {
    printf("参数i有误！\n");
    return 0;
  }
  s = (Lnode *)malloc(sizeof(Lnode));
  s->data = p->data;
  p->data = x;
  s->next = p->next;
  p->next = s;
  return 1;
}

// 单链表删除
int Delete_LinkList(LinkList L, int i) 
{
  Lnode *p, *q;
  p = Get_LinkList(L, i - 1);
  if (p == NULL || p->next == NULL) 
  {
    printf("参数i有误！\n");
    return 0;
  }
  q = p->next;
  // 把下个结点的指针域赋值给上个结点的指针域
  p->next = q->next;
  free(q);
  return 1;
}

// 单向循环链表连接操作，链表有头结点
LinkList Connect_LinkList(LinkList r1, LinkList r2) 
{
  LinkList q = r1->next;
  while (q->next != NULL) 
  {
    q = q->next;
  }
  q->next = r2->next->next;
  free(r2->next);
  // 首尾连接
  r2->next = q;
  return r1;
}


int main()
{
  LinkList ll = Create_LinkList();
  // LinkList ll2 = Create_LinkList2();
  int llLen = Length_LinkList(ll);
  printf("llLen: %d\n", llLen);
  free(ll);
  // free(ll2);
  return 0;
}



// 创建一个带头结点的链表
LinkList Create_LinkList3() 
{
  LinkList L = (Lnode *)malloc(sizeof(Lnode));
  L->next = NULL;
  Lnode *r = L;
  Lnode *s;
  DataType e;
  scanf("%d", &e);
  while (e != flag) {
    s = (Lnode *)malloc(sizeof(Lnode));
    s->data = e;
    r->next = s;
    r = s;
    scanf("%d", &e);
  }
  r->next = NULL;
  return L;
}